﻿using Arbol_2;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Windows.Forms;
//using Microsoft.Office.Interop.Word;
using System.IO;
using System.ComponentModel;
using System.Data;


namespace Arbol
{
    static class Program
    {
        /// <summary>
        /// Punto de entrada principal para la aplicación.
        /// </summary>
        [STAThread]
        static void Main()
        {
           
            Application.EnableVisualStyles();
            Application.SetCompatibleTextRenderingDefault(false);
            Form1 f1 = new Form1();
            Application.Run(f1);
            FPGrowth fpg = new FPGrowth();
        }
    }

    
public struct FrequentItems
{
internal short fequency;
internal string itemName;
}

struct Fptree
{
public string parent;
public string node;
public string child;
public short wight;
}

struct GeneratedRules
{
public double item1Support;
public int item2Support;
public double confidence;
public string item1;
public string item2;
}



class FPGrowth
{
//-----------------------
System.Collections.ArrayList list;
string itemOrder;
Fptree[] tree;
Fptree[] conditionalFPTree;

GeneratedRules[] rules = new GeneratedRules[10]; //store top ten patterns generated by FP Growth algorithm
string frequentPatterns;
int q = 0;
//-----------------------

RichTextBox richTextBox1 = new RichTextBox();
DataGridView dataGridView1 = new DataGridView();

public static System.Data.DataSet ds = new System.Data.DataSet();
//DataTable dt;

//DataRow dr;
//int columnNames;

int numberOfItemInDB = 0;

//________________FPTree___
int treeSize = 0;
FrequentItems[] frequentItemList;
int frequentItemListSize = 0;
int maxNumberOfItems; //maximum number of item containing transaction item length
// FPTree[] tree;

public static double min_support = 3;
public static double min_confidence = 0.5;
//________________________________

public static string databaseName = "db";
public static string tableName= "tabla";

private int numberOfWords(string[] lineReading)
{
int numberOfWord = 0;
foreach (string s in lineReading)
{
if (!s.Equals(" "))
numberOfWord++;
}
return numberOfWord;
} 

private void StartButton_Click_1(object sender, EventArgs e)//start association using selected algorithm
{
richTextBox1.Clear();
numberOfItemInDB = 0;
System.Collections.ArrayList _items = scanDataBase();
insertFrequentItems(_items, numberOfItemInDB - calcutatMinSupport(_items));
frequentItemsOrder();
// Display(_items); //display FP Tree

//--------------------------

initParrentArray();
list = new System.Collections.ArrayList();
richTextBox1.Text = "=== Run information ===";
richTextBox1.Text += "\n\n\n\nScheme : " + databaseName;
richTextBox1.Text += "\nRelation : " + tableName;
richTextBox1.Text += "\nInstance : " + dataGridView1.RowCount;
richTextBox1.Text += "\n\nAttribute : ";
for (int r = 0; r < frequentItemList.Length; r++)// frequentItemSet
{
richTextBox1.Text += "\n\t " + frequentItemList[r].itemName;
itemOrder += frequentItemList[r].itemName + ',';
}
//rules.Add()
richTextBox1.Text += "\n\n\n====== Associator model (full training set) ======";
// richTextBox1.SelectionFont = new System.Drawing.Font("Algerian", 11, FontStyle.Underline);
// richTextBox1.SelectedText = "\n\n\n=== Associator model (full training set) ===";
richTextBox1.Font = new System.Drawing.Font("Times New Roman", 10, System.Drawing.FontStyle.Regular);

// richTextBox1.Font = new System.Drawing.Font("DFKai-SB", 10, FontStyle.Regular);

tree = new Fptree[treeSize];//numberOfItems
int lastColumn = dataGridView1.ColumnCount - 1;

int j = 0;

int countRow = 0;

do
{
drowFPTree(dataGridView1.Rows[countRow].Cells[lastColumn].Value.ToString().TrimEnd(' ').Split(','), ref tree, ref j);
countRow++;
} while (dataGridView1.RowCount > countRow);

Array.Resize<Fptree>(ref tree, j); ///chenge the size of the array

displayTree(tree);

conditionalPatternBase(frequentItemList);

DateTime time = DateTime.Now;

// textBox1.Text = time.Hour.ToString() + ":" + time.Minute.ToString() + ":" + time.Second.ToString();

//--------------------------
// textBox1.Text += 
}

//--------------------------Start Conditional Fp Tree------------------------

private void conditionalPatternBase(FrequentItems[] frequentItemSet)
{
char[] root = new char[] { 'S', 't', 'a', 'r', 't' };

for (int i = frequentItemSet.Length - 1; i > -1; i--)
{
conditionalFPTree = new Fptree[tree.Length]; //for worest case 
int index = 0;

for (int j = 0; j < tree.Length; j++)
{
if (tree[j].node.Equals(frequentItemSet[i].itemName))//conditional pattern for each item
{
if (!tree[j].parent.Equals("Start-"))
{
for (int h = 0; h < tree[j].wight; h++)
{
drowFPTree((tree[j].parent + frequentItemSet[i].itemName).TrimStart(root).TrimStart('-').Split('-'), ref conditionalFPTree, ref index);
}
}
}
}

Array.Resize<Fptree>(ref conditionalFPTree, index); ///chenge the size of the array

richTextBox1.Text += "\n\n\n\t ********* Conditional FP Tree for " + frequentItemSet[i].itemName + " *********";
displayTree(conditionalFPTree);
findFrequentItemSets(frequentItemSet[i].itemName);
}
// sortRules();
richTextBox1.Text += displayArray();//display Rules
}

private void findFrequentItemSets(string item)
{
string temp = "";
int support = 0;
frequentPatterns = "";
for (int j = 1; j < conditionalFPTree.Length; j++)
{
temp = conditionalFPTree[j].node;

for (int k = 1; k < conditionalFPTree.Length; k++)
{
if (conditionalFPTree[k].node == temp)//conditional pattern for each item
{
support += conditionalFPTree[k].wight;
}
}
if (support >= min_support && !frequentPatterns.Contains(temp) && temp != item)
frequentPatterns += temp + ',';
support = 0;
frequentPatterns.TrimEnd(',');

}
generateFrequentPattern(frequentPatterns.TrimEnd(','), item);
}

private void generateFrequentPattern(string freqPattern, string itemName)
{
// GeneratedRules[] rule = new GeneratedRules[1];

list.Clear();//An array store all possible combnations of frequent item sets
creatCombination(freqPattern, list);
// displayList(list);
int temp_support = 0;

richTextBox1.Text += "\n\n\t Frequent pattern set for " + itemName + " { ";

for (int i = 0; i < list.Count; i++)
{
temp_support = getSupport(conditionalFPTree, itemName, list[i].ToString());//suport of all possible frequent item sets combination one by one
if (temp_support >= min_support)
{
richTextBox1.Text += list[i].ToString() + ',' + itemName + ':' + temp_support + " "; //pattern
calculateConfidence(list[i].ToString() + ',' + itemName, temp_support);
}
// temp_support = 0;
}

richTextBox1.Text += '}';
}

///---------------------calculat Confidence ---------------

private void calculateConfidence(string patternList, int item2_support)
{
string item1 = "";
string item2 = "";
string lastItem = "";
//MessageBox.Show("Pattern for ------> "+ patternList);
string[] tempPatterns = patternList.Split(',');
double item1_support = 0.0;
double confidence = 0.0;
for (int w = tempPatterns.Length - 1; w > -1; w--)
{
item1 = "";
item2 = "";
foreach (string _pattern in tempPatterns)
{
if (tempPatterns[w] != _pattern && !tempPatterns[w].Equals(""))
item1 += _pattern + ',';
else if (!tempPatterns[w].Equals(""))
item2 = tempPatterns[w];
}
if (item1.TrimEnd(',').Split(',').Length > 1)//For mony to 1 like a,b,c..--->h
{
item1 = getLastItem(itemOrder, item1);
//string jjj = item1 + "---->" + item2;
lastItem = item1.TrimEnd(',').Split(',')[tempPatterns.Length - 2];
item1 = item1.Remove(item1.LastIndexOf(lastItem));
// MessageBox.Show(jjj+"\nitem1 : " + item1 +"\tLast Item : "+lastItem);
item1_support = getSupport(tree, lastItem, item1);
confidence = item2_support / item1_support;

//string hhhhh = "item 1 Support : " +item1_support.ToString() + "item 2 Support : " + item2_support.ToString()+"\n";

// MessageBox.Show(hhhhh+item1+lastItem + "---->" + item2 + " : " + confidence.ToString());
if (confidence > min_confidence)
storeTopTenPatterns(item1 + lastItem, item2, item1_support, item2_support, confidence);
}
else//for 1 to 1 like B--->C
{
item1_support = 0;
for (int z = 0; z < tree.Length; z++)
{
if (tree[z].node.Equals(item1.TrimEnd(',')))
item1_support += tree[z].wight;
}
confidence = item2_support / item1_support;
if (confidence > min_confidence)
storeTopTenPatterns(item1, item2, item1_support, item2_support, confidence);
}
}

}
private string getLastItem(string order, string unOrderdItem)
{
string lastItem = "";
foreach (string singleItem in order.Split(','))
{
if (unOrderdItem.Contains(singleItem) && !singleItem.Equals(""))
lastItem += singleItem + ',';
}
return lastItem;
}

private void storeTopTenPatterns(string newItem1, string newItem2, double item1_supp, int item2_supp, double confi)
{
if (q < 10)
{
if (rules[q].item1.Equals(String.Empty) && rules[q].item2.Equals(String.Empty)) // 
{
rules[q].item1 = newItem1.TrimEnd(',');
rules[q].item2 = newItem2;
rules[q].item1Support = item1_supp;
rules[q].item2Support = item2_supp;
rules[q].confidence = item2_supp / item1_supp;
}
q++;
}
else
{
int k = getMinimumConfidence(confi);
if (k > -1 && rules[k].confidence < confi)
{
rules[k].item1 = newItem1.TrimEnd(',');
rules[k].item2 = newItem2;
rules[k].item1Support = item1_supp;
rules[k].item2Support = item2_supp;
rules[k].confidence = item2_supp / item1_supp;
}
}
}

private int getMinimumConfidence(double minConf)//return minimum confidence item in the rules array
{
for (int t = 0; t < 10; t++)
{
if (rules[t].confidence < minConf)
return t;
}
return -1;
}

private void initParrentArray()
{
for (int v = 0; v < 10; v++)
{
rules[v].item1 = "";
rules[v].item2 = "";
rules[v].item1Support = 0;
rules[v].item2Support = 0;
rules[v].confidence = 0;
}
}

private string displayArray()
{
sortRules();
string temp = "";
string tempdisp = "";
int lastIndex = -1;
int number = 1;
for (int u = 0; u < 10; u++)
{
if (!rules[u].item1.Equals(String.Empty) && !rules[u].item2.Equals(String.Empty))
{
temp = "";
if (number == 10)
temp += number.ToString();
else
temp += number.ToString() + " ";
tempdisp += temp + ". [ " + rules[u].item1 + "] : " + rules[u].item1Support + " ====> [ " + rules[u].item2 + " ] : "
+ rules[u].item2Support + " < conf : (" + rules[u].confidence + ") >\n";
lastIndex = u;
number++;
}
}
lastIndex++;
return "\n\nFPGrowth Algorithm generated top " + lastIndex + " rules \n\n" + tempdisp;
//MessageBox.Show(outputString);
}

///---------------------End confidence calculation--------------

///---------------------Combination of n item ----------------------

private void creatCombination(string frequentItem, System.Collections.ArrayList list)
{
string items = "";
int r = 2;
string temp = "";
int k = 0;
string[] f_item = frequentItem.TrimEnd(',').Split(',');
items = frequentItem.TrimEnd(',');
//int count = frequentItem.TrimEnd(',').Split(',').Length;
int count = f_item.Length;

for (int i = 0; i < count; i++)
{
list.Add(f_item[i]);
}

if (count > 1)
{
int comb = getCombination(count, r);

while (comb >= 1)
{
for (int i = k; i < list.Count; i++)
{
temp = list[i].ToString();

foreach (string s in items.Split(','))
{
if (temp.Equals(s))
continue;
else
{
temp = sortItem(temp + ',' + s, items).TrimEnd(',');
if (!isExist(list, temp))
list.Add(temp);
}
temp = list[i].ToString();
}
}
k += comb;
r++;
comb = getCombination(count, r);
}
}
}

private string sortItem(string _item, string freItem)
{
string temp = "";
foreach (string s in freItem.Split(','))
{
if (_item.Contains(s))
temp += s + ',';
}
return temp.TrimEnd();
}

private bool isExist(System.Collections.ArrayList _list, string newItem)
{
for (int j = 0; j < _list.Count; j++)
{
if (_list[j].ToString().Equals(newItem))
return true;
}
return false;
}

private int getCombination(int n, int r)
{
int denominator = (getFactorial(n - r) * getFactorial(r));
return getFactorial(n) / denominator;
}

private int getFactorial(int num)
{
int fac = 1;
for (int i = 2; i <= num; i++)
fac *= i;
return fac;
} 
///------------------ combnation function end-------------------------

///---------------------calculat minimum support -------------------

private int getSupport(Fptree[] _tree, string childName, string parents)//Get support from conditional FP Tree
{
int support = 0;
bool pathExist = false;
for (int c = _tree.Length - 1; c > -1; c--)
{
if (_tree[c].node.Equals(childName))// && conditionalFPTree[c].parent.Contains(_parent))
{
foreach (string par in parents.TrimEnd(',').Split(','))
{
if (!par.Equals(String.Empty))
{
if (_tree[c].parent.TrimEnd('-').Split('-').Contains(par))
pathExist = true;
else
{
pathExist = false;
break;
}
}
}
if (pathExist)
{
support += _tree[c].wight;
pathExist = false;
}
}
}
return support;
}

///---------------------end min support calculation-----------------

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

//--------------------------Draw FP Tree-------------------------------------

private void drowFPTree(string[] tran1, ref Fptree[] treeFP, ref int j)//j is index of the array
{
int m = 0;
string tempParent = "";

for (int k = 0; k < tran1.Length; k++)
{
if (j == 0)
{
treeFP[0].parent = "";
treeFP[0].node = "Start-";
treeFP[0].wight = 0;
treeFP[0].child = tran1[k];

tempParent += "Start-";
treeFP[++j].parent = tempParent;
treeFP[j].node = tran1[k];
treeFP[j].wight++;
if (k + 1 < tran1.Length)
treeFP[j].child = tran1[k + 1];
else
treeFP[j].child = "";

j++;
}
else if (k == 0)
{
m = isRootChild(treeFP, j, tran1[k]);

if (m >= 0)//if exist
{
treeFP[m].wight++;
tempParent = "Start-";
}
else //New root node child
{
tempParent = "Start-";
treeFP[j].parent = tempParent;
treeFP[j].node = tran1[k];
treeFP[j].wight++;
if (k + 1 < tran1.Length)
treeFP[j].child = tran1[k + 1];
else
treeFP[j].child = "";
j++;
}
}
else
{
tempParent += tran1[k - 1] + '-';
if (k + 1 < tran1.Length)
treeFP[j].child = tran1[k + 1];
else
treeFP[j].child = "";

m = ischild(treeFP, tempParent, tran1[k], j);

if (m >= 0)//if exist
{
treeFP[m].wight++;
// tempParent = "Start" + treeFP[m - 1].node;
}
else
{
treeFP[j].parent = tempParent;
treeFP[j].node = tran1[k];
treeFP[j].wight++;
j++;
}
}
}
}

private int ischild(Fptree[] _tree, string tempParent, string item, int length)
{
for (int i = 0; i < length; i++)
{
if (_tree[i].parent == tempParent && _tree[i].node == item)
return i;
}
return -1;
}

private int isRootChild(Fptree[] _tree, int lastindex, string item)
{

for (int i = 0; i < lastindex; i++)
{
if (_tree[i].parent == "Start-" && _tree[i].node == item)
{
return i;
}
}
return -1;
}

private void displayTree(Fptree[] _tree)
{
string s = "";
for (int i = 0; i < _tree.Length; i++)
{
s += "\n\nNode Name : " + _tree[i].node + "\nParent : " + _tree[i].parent
+ "\nChild : " + _tree[i].child + "\nWight : " + _tree[i].wight;
}
richTextBox1.Text += "\n\n" + s;
}

//--------------------------end drawing -------------------------------------

///--------------------Sort Rule -------------------------------\

private void sortRules()
{
string tempItem1 = "";
string tempItem2 = "";
int tempSupport2 = 0;
double tempSupport1 = 0.0;

int index = 0, j = -1;
double tempConfidence;
while (index < 10)
{
tempConfidence = -1;
for (int k = index; k < 10; k++)
{
if (rules[k].confidence >= tempConfidence)
{
tempConfidence = rules[k].confidence;
j = k;
}
}
tempItem1 = rules[index].item1;
tempItem2 = rules[index].item2;
tempSupport1 = rules[index].item1Support;
tempSupport2 = rules[index].item2Support;

rules[index].item1 = rules[j].item1;
rules[index].item2 = rules[j].item2;
rules[index].item1Support = rules[j].item1Support;
rules[index].item2Support = rules[j].item2Support;
rules[index++].confidence = rules[j].confidence;

rules[j].item1 = tempItem1;
rules[j].item2 = tempItem2;
rules[j].item1Support = tempSupport1;
rules[j].item2Support = tempSupport2;
rules[j].confidence = rules[j].item2Support / rules[j].item1Support;
}
}

///--------------------End Sorting -----------------------------

//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

private void frequentItemsOrder()//fill datagridview with Frequent Items Order of each transactions
{
treeSize = 0;
string temp = "";
for (int m = 0; m < dataGridView1.Rows.Count; m++)
{
for (int n = 0; n < frequentItemList.Length; n++)
{
for (int col = 0; col < dataGridView1.ColumnCount - 1; col++)
{
if (dataGridView1.Rows[m].Cells[col].Value.ToString().TrimEnd(' ').Equals(frequentItemList[n].itemName) && frequentItemList[n].itemName != null)
temp += frequentItemList[n].itemName + ',';
}
}
if (maxNumberOfItems < temp.TrimEnd(',').Length)
maxNumberOfItems = temp.TrimEnd(',').Length;

dataGridView1.Rows[m].Cells[dataGridView1.ColumnCount - 1].Value = temp.TrimEnd(',');
if (temp != "")
treeSize += temp.TrimEnd(',').Split(',').Length;
temp = "";
}
// MessageBox.Show(""+treeSize);
// dataGridView1.Rows[dataGridView1.Rows.Count - 1].Cells[dataGridView1.ColumnCount - 1].Value = temp.TrimEnd(',');
}

private void insertFrequentItems(System.Collections.ArrayList items, int size)//insert the items in frequent item list array
{
frequentItemListSize = size;
frequentItemList = new FrequentItems[size];
items.Sort();
int j = 0;
string newItem = "";
foreach (string item in items)
{
if (!item.Equals(newItem))
{
newItem = item;
frequentItemList[j].itemName = item;
frequentItemList[j].fequency++;
j++;
}
else
frequentItemList[j - 1].fequency++;
}

sortFrequentItemList();
}

private int nextMaximum(int startindex)
{
short max_frequency = -1;
int Max_index = -1;
for (int i = startindex; i < frequentItemList.Length; i++)
{
if (frequentItemList[i].fequency > max_frequency)
{
max_frequency = frequentItemList[i].fequency;
Max_index = i;
}
}
return Max_index;
}

private void sortFrequentItemList()
{
short tempfrequency = 0;
string tempItemName = "";
int index = 0;
for (int j = 0; j < frequentItemList.Length; j++)
{
index = nextMaximum(j);

if (index > -1 && frequentItemList[index].fequency >= Convert.ToInt32(min_support))
{
tempfrequency = frequentItemList[j].fequency;
tempItemName = frequentItemList[j].itemName;
frequentItemList[j].fequency = frequentItemList[index].fequency;
frequentItemList[j].itemName = frequentItemList[index].itemName;

frequentItemList[index].fequency = tempfrequency;
frequentItemList[index].itemName = tempItemName;
}
}
}

private int calcutatMinSupport(System.Collections.ArrayList items)//Find items > given minimum support and return removed number of items
{
items.Sort();
int count = 0;
string itemName = String.Empty;

int NoRemovedItem = 0;//list of item to be removed

string removeList = String.Empty;//list of item to be removed

foreach (string singleItem in items)
{
if (!singleItem.Equals(itemName))
{
if (itemName != String.Empty && count < Convert.ToInt32(min_support))
{
removeList += itemName + ',';
NoRemovedItem++;
}
itemName = singleItem;
count = 1;
}
else
count++;
}
if (itemName != String.Empty && count < Convert.ToInt32(min_support)) // for the last item with in the items arraylist
{
removeList += itemName;
NoRemovedItem++;
}
// MessageBox.Show(removeList);
removeItems(removeList, items);
return NoRemovedItem;
}

private void removeItems(string _itemNames, System.Collections.ArrayList _items)//remove items < given minimum support
{
foreach (string s in _itemNames.Split(','))
{
while (_items.Contains(s))
_items.Remove(s);
}
}

private System.Collections.ArrayList scanDataBase()
{
System.Collections.ArrayList items = new System.Collections.ArrayList();//Temporarly store all items from DB

for (int i = 0; i < dataGridView1.RowCount; i++)
{
for (int column = 0; column < dataGridView1.ColumnCount - 1; column++)
{
if (!dataGridView1.Rows[i].Cells[column].Value.ToString().TrimEnd(' ').Equals(String.Empty))
{
if (!items.Contains(dataGridView1.Rows[i].Cells[column].Value.ToString().TrimEnd(' ')))
numberOfItemInDB++;

items.Add(dataGridView1.Rows[i].Cells[column].Value.ToString().TrimEnd(' '));// if column 0 is trsansaction row
}
}
}
// MessageBox.Show(numberOfItemInDB.ToString());
// Display(items);
return items;
}

}
}
